from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 下 上 左 右
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        n = len(word)
        rows, cols = len(board), len(board[0])
        # 初始化访问标记数组
        visited = [[False] * cols for _ in range(rows)]

        # 深度优先搜索函数
        def dfs(x, y, k):
            # 如果已经匹配到单词的最后一个字符，返回 True
            if k == n - 1:
                return board[x][y] == word[k]
            # 如果当前字符不匹配，返回 False
            if board[x][y] != word[k]:
                return False
            # 标记当前位置为已访问
            visited[x][y] = True
            # 尝试四个方向
            for i in range(4):
                xx = x + dx[i]
                yy = y + dy[i]
                # 检查新位置是否合法且未被访问
                if 0 <= xx < rows and 0 <= yy < cols and not visited[xx][yy]:
                    # 递归调用 dfs
                    if dfs(xx, yy, k + 1):
                        return True
            # 回溯，将当前位置标记为未访问
            visited[x][y] = False
            return False

        # 遍历矩阵中的每个元素
        for i in range(rows):
            for j in range(cols):
                if dfs(i, j, 0):
                    return True
        return False